package com.formula.datastructure.exam.other;

import com.formula.datastructure.util.DataUtil;

public class MaxK {
    public Integer[] maxK(Integer[] array, int k) {
        Integer[] result = new Integer[k];

        int N = array.length;

        for (int i = N / 2; i >= 0; i--) {
            siftDown(array, i, N);
        }

        int count = 0;
        for (int i = N - 1; i >= N - k; i--) {
            result[count++] = array[0];
            array[0] = array[i];
            array[i] = result[count - 1];
            siftDown(array, 0, i);
        }

        return result;
    }

    private void siftDown(Integer[] array, int idx, int length) {
        Integer temp;
        for (int i = getLeft(idx); i < length; i = getLeft(idx)) {
            if (i + 1 < length && array[i + 1] > array[i]) {
                i = i + 1;
            }
            if (array[i] <= array[idx]) {
                break;
            } else {
                temp = array[idx];
                array[idx] = array[i];
                array[i] = temp;
                idx = i;
            }
        }
    }

    private int getLeft(int idx) {
        return 2 * idx + 1;
    }

    public static void main(String[] args) {
        MaxK cal = new MaxK();

        int size = 20;
        int range = 999;
        Integer[] array = DataUtil.genUniqueArray(size, range);
        DataUtil.printIndex(size);
        DataUtil.printArray(array);
        DataUtil.printArray(cal.maxK(array, 8));
    }
}
